package com.fufu.algorithem.recursion;

import java.util.Arrays;

/**
 * @author: BlcakTiger
 * @date: 2023/2/19 20:19
 * @contact: hsf6661@163.com
 */
public class EightQueue1 {

    //皇后数量
    int queueCount = 8;
    //模拟棋盘：索引表达行，值表示列
    int[] arr = new int[queueCount];
    //计数
    int count = 0;

    public static void main(String[] args) {
        EightQueue1 queue1 = new EightQueue1();
        queue1.placeQueue(0);
        System.out.println(queue1.count);
    }

    public void placeQueue(int n){
        //因为是从第0个queue开始的，所以n等于8时，表示已经已经成功放入了8个皇后，可以将当前递归分支结束
        if (n == queueCount){
            print();
            count++;
            return;
        }

        //每次放置都是从第一列开始放，依次往后放，这里遍历的就是每一列
        for (int i = 0; i < queueCount; i++) {
            //将queue放在第i列
            arr[n] = i;
            //判断皇后是否冲突
            if(judge(n)){
                //若不冲突，放下一个皇后
                placeQueue(n+1);
            }
            //如果冲突，试试将皇后摆在当前行的后面一列
        }
    }


    private boolean judge(int n){
        //这里是遍历行，用n前面的每一行的皇后摆放位置与当前行的摆放位置比较
        for (int i = 0; i < n; i++) {
            //因为是按行依次摆放，一定不会摆在同一行，所以只判断是否在同一列或同一直线即可
            //arr[i]==arr[n] 比较列值
            //Math.abs(n-i) == Math.abs(arr[n]-arr[i]) 因为列和行都是1个单位的等差，所以，当两个皇后在同一条直线上
            //这两个皇后构成的三角形斜率为1，故而行差==列差
            if (arr[i]==arr[n] || Math.abs(n-i) == Math.abs(arr[n]-arr[i])){
                return false;
            }
        }
        return true;
    }

    public void print(){
        System.out.println(Arrays.toString(arr));
    }
}
